home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 016a / gofer221.zip / GRAMMAR.DOC < prev    next >
Text File  |  1991-11-20  |  9KB  |  155 lines
  1.  --------------------------------------------------------------------------
  2.  Input form as parsed:
  3.  --------------------------------------------------------------------------
  4.  Rhs     ::= GUARDED [(Line,(Expr,Expr))]  Expr::= LETREC [Binding] Expr
  5.           |  LETREC  [Binding] Rhs              |  COND Expr Expr Expr
  6.           |  (Line, Expr)                       |  AP Expr Expr
  7.           ;                                     |  NAME
  8.                                                 |  VAR
  9.                                                 |  INT
  10.  Eqn     ::= SIGDECL Line [Var] Type            |  STRING
  11.           |  (Expr, Rhs)                        |  CHAR
  12.           ;                                     |  UNIT
  13.                                                 |  TUPLE
  14.  Qual    ::= FROMQUAL (Pat,Expr)                |  TCHARCELL
  15.           |  QWHERE   (Pat,Expr)                |  LAMBDA Alt
  16.           |  BOOLQUAL Expr                      |  FINSTEPSEQ (e1,e2,e3)
  17.           ;                                     |  FINSEQ (e1,e2)
  18.                                                 |  INFSTEPSEQ (e1,e2)
  19.  Alt     ::= ([Pat], Rhs)                       |  INFSEQ e1
  20.           ;                                     |  ESIGN e1 Type
  21.                                                 |  CASE (Expr,[(Pat,Rhs)])
  22.                                                 |  FINLIST [Expr]
  23.                                                 |  LISTCOMP Expr [Qual]
  24.                                                 ;
  25.  
  26.  --------------------------------------------------------------------------
  27.  After translation from equations to bindings:
  28.  --------------------------------------------------------------------------
  29.  Rhs     ::= GUARDED [(Line,(Expr,Expr))]  Expr::= LETREC [Binding] Expr
  30.           |  LETREC  [Binding] Rhs              |  COND Expr Expr Expr
  31.           |  (Line, Expr)                       |  AP Expr Expr
  32.           ;                                     |  NAME
  33.                                                 |  VAR
  34.                                                 |  INT
  35.  Binding ::= (Var, (Type, [Alt]))               |  STRING
  36.           |  ([Var], ([Type], (Pat,Rhs)))       |  CHAR
  37.           ;                                     |  UNIT
  38.                                                 |  TUPLE
  39.  Qual    ::= FROMQUAL (Pat,Expr)                |  TCHARCELL
  40.           |  QWHERE   (Pat,Expr)                |  LAMBDA Alt
  41.           |  BOOLQUAL Expr                      |  FINSTEPSEQ (e1,e2,e3)
  42.           ;                                     |  FINSEQ (e1,e2)
  43.                                                 |  INFSTEPSEQ (e1,e2)
  44.  Alt     ::= ([Pat], Rhs)                       |  INFSEQ e1
  45.           ;                                     |  ESIGN e1 Type
  46.                                                 |  CASE (Expr,[(Pat,Rhs)])
  47.                                                 |  FINLIST [Expr]
  48.                                                 |  LISTCOMP Expr [Qual]
  49.                                                 ;
  50.  
  51.  --------------------------------------------------------------------------
  52.  After dependency analysis:
  53.  --------------------------------------------------------------------------
  54.  Rhs     ::= GUARDED [(Line,(Expr,Expr))]  Expr::= LETREC [[Binding]] Expr
  55.           |  LETREC  [[Binding]] Rhs            |  COND Expr Expr Expr
  56.           |  (Line, Expr)                       |  AP Expr Expr
  57.           ;                                     |  NAME
  58.                                                 |  VAR
  59.                                                 |  INT
  60.  Binding ::= (Var, (Type, [Alt]))               |  STRING
  61.           |  ([Var], ([Type], (Pat,Rhs)))       |  CHAR
  62.           ;                                     |  UNIT
  63.                                                 |  TUPLE
  64.  Qual    ::= FROMQUAL (Pat,Expr)                |  TCHARCELL
  65.           |  QWHERE   (Pat,Expr)                |  LAMBDA Alt
  66.           |  BOOLQUAL Expr                      |  FINSTEPSEQ (e1,e2,e3)
  67.           ;                                     |  FINSEQ (e1,e2)
  68.                                                 |  INFSTEPSEQ (e1,e2)
  69.  Alt     ::= ([Pat], Rhs)                       |  INFSEQ e1
  70.           ;                                     |  ESIGN e1 Type
  71.                                                 |  CASE (Expr,[(Pat,Rhs)])
  72.                                                 |  FINLIST [Expr]
  73.                                                 |  LISTCOMP Expr [Qual]
  74.                                                 ;
  75.  
  76.  --------------------------------------------------------------------------
  77.  After type checking:
  78.  --------------------------------------------------------------------------
  79.  Rhs     ::= GUARDED [(Line,(Expr,Expr))]  Expr::= LETREC [[Binding]] Expr
  80.           |  LETREC  [[Binding]] Rhs            |  COND Expr Expr Expr
  81.           |  (Line, Expr)                       |  AP Expr Expr
  82.           ;                                     |  NAME
  83.                                                 |  VAR
  84.                                                 |  INT
  85.  Binding ::= (Var, [Alt])                       |  STRING
  86.           |  ([Var], (Pat,Rhs))                 |  CHAR
  87.           ;                                     |  UNIT
  88.                                                 |  TUPLE
  89.  Qual    ::= FROMQUAL (Pat,Expr)                |  TCHARCELL
  90.           |  QWHERE   (Pat,Expr)                |  LAMBDA Alt
  91.           |  BOOLQUAL Expr                      |  FINSTEPSEQ (e1,e2,e3)
  92.           ;                                     |  FINSEQ (e1,e2)
  93.                                                 |  INFSTEPSEQ (e1,e2)
  94.  Alt     ::= ([Pat], Rhs)                       |  INFSEQ e1
  95.           ;                                     |  ESIGN e1 Type
  96.                                                 |  CASE (Expr,[(Pat,Rhs)])
  97.                                                 |  FINLIST [Expr]
  98.                                                 |  LISTCOMP Expr [Qual]
  99.                                                 ;
  100.  
  101.  --------------------------------------------------------------------------
  102.  After translation to remove list comprehensions, pattern bindings,
  103.  sequence expressions, line number references, case and lambda expressions,
  104.  type signature expressions:
  105.  --------------------------------------------------------------------------
  106.  Rhs     ::= GUARDED [(Expr,Expr)]      Expr  ::= LETREC [Binding] Expr
  107.           |  LETREC  [Binding] Rhs             |  COND Expr Expr Expr
  108.           |  Expr                              |  AP Expr Expr
  109.           ;                                    |  NAME
  110.                                                |  VAR
  111.  Binding ::= (Var, [Alt])                      |  INT
  112.           ;                                    |  STRING
  113.                                                |  CHAR
  114.  Alt     ::= ([Pat], Rhs)                      |  UNIT
  115.           ;                                    |  TUPLE
  116.                                                ;
  117.  
  118.  --------------------------------------------------------------------------
  119.  After pattern matching compiler: replace Alts by CASE & NUMCASE, separate
  120.  function and variable bindings, calculate free variable sets and local
  121.  function dependents for later use in lambda lifting:
  122.  --------------------------------------------------------------------------
  123.  Rhs      ::= GUARDED [(Expr, Expr)]    Expr  ::= LETREC LocalDef Expr
  124.            |  LETREC  LocalDef Rhs             |  COND Expr Expr Expr
  125.            |  Expr                             |  AP Expr Expr
  126.            |  FATBAR  Rhs Rhs                  |  NAME
  127.            |  CASE    OFFSET [(Discr,Rhs)]     |  VAR
  128.            |  NUMCASE OFFSET [(Discr,Rhs)]     |  INT
  129.            ;                                   |  STRING
  130.  LocalDef ::= ([Rhs], [FunDef])                |  CHAR
  131.            ;                                   |  OFFSET
  132.  FunDef   ::= (Var, Arity, (Fvs, FFs, Rhs))    |  UNIT
  133.            ;                                   |  TUPLE
  134.                                                ;
  135.  Fvs is a list of free variables (i.e. offsets) appearing in Rhs,
  136.  FFs is a list of free functions (i.e. FunDefs) appearing in Rhs and
  137.  contained in the same group of FunDefs.
  138.  --------------------------------------------------------------------------
  139.  Scope    ::= [(Var,Expr)]               Switch ::= ([Pat], Scope, Rhs)
  140.            ;                                     ;
  141.  --------------------------------------------------------------------------
  142.  Lifted   ::= GUARDED [(LTerm, LTerm)]   LTerm ::= LETREC [Lifted] LTerm
  143.            |  LETREC  [Lifted] Lifted           |  COND   LTerm LTerm LTerm
  144.            |  LTerm                             |  AP     LTerm LTerm
  145.            |  FATBAR  Lifted Lifted             |  NAME
  146.            |  CASE    OFFSET [(Discr,Lifted)]   |  VAR
  147.            ;                                    |  INT
  148.                                                 |  STRING
  149.                                                 |  CHAR
  150.                                                 |  OFFSET
  151.                                                 ;
  152.  
  153.  --------------------------------------------------------------------------
  154.  
  155.